//
//  45.扑克牌顺子.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/28.
//

import Foundation
/*
 题目：现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
      有如下规则：
      1. A为1，J为11，Q为12，K为13，A不能视为14
      2. 大、小王为 0，0可以看作任意牌
      3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
      例如：给出数据[6,0,2,0,4]
      中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4]
      这样这五张牌在[2,6]区间连续，输出true
      数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]
 思路1：Set+遍历
        我们分两种情况考虑，
        一. 如果vector中不包含0的情况：
        那么如何判断呢？因为需要是顺子，所以首先不能有重复值， 如果没有重复值，那么形如[1 2 3 4 5]
        [5 6 7 8 9]， 会发现最大值与最小值的差值应该小于5.
        
        二. 如果vector中包含0：
        发现除去0后的值，判断方法和1中是一样的。
        
        所以根据如上两个条件，算法过程如下：
        
        初始化一个set，最大值max_ = 0, 最小值min_ = 14
        遍历数组， 对于大于0的整数，没有在set中出现，则加入到set中，同时更新max_, min_
        如果出现在了set中，直接返回false
        数组遍历完，最后再判断一下最大值与最小值的差值是否小于5
 思路2：排序+遍历
        排序过后相同的数字肯定是相邻的
        0不算最小值，遇到跳过
 */
func offer_45() {
    print(Solution().IsContinuous2([5,0,2,0,4]
))
}

fileprivate class Solution {
    func IsContinuous1(_ numbers: [Int]) -> Bool {
        guard numbers.count == 5 else { return false }
        var maxNum = 0, minNum = 14
        var st = Set<Int>()
        for num in numbers {
            if num > 0 {
                if st.contains(num) { return false }
                st.insert(num)
                maxNum = max(maxNum, num)
                minNum = min(minNum, num)
            }
        }
        return maxNum - minNum < 5
    }
    
    func IsContinuous2(_ numbers: [Int]) -> Bool {
        guard numbers.count == 5 else { return false }
        let numbers = numbers.sorted()
        var minIndex = 0
        for i in 0..<numbers.count {
            if numbers[i] == 0 {
                minIndex += 1
                continue
            }
            if i+1 < numbers.count && numbers[i] == numbers[i+1] {
                return false
            }
        }
        return numbers.last! - numbers[minIndex] < 5
    }
}

